package lianbiao;

import java.util.*;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 17:35
 * description:跳表
 */

/**
 * 跳表节点类
 */
class SkipListNode {
    Integer key;
    SkipListNode[] forward;

    public SkipListNode(Integer key, int level) {
        this.key = key;
        this.forward = new SkipListNode[level + 1];
    }

    @Override
    public String toString() {
        return "SkipListNode(key=" + key + ")";
    }
}

/**
 * 跳表实现类
 */
class SkipList implements Iterable<Integer> { // 实现Iterable接口
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    private int level;
    private SkipListNode header;
    private Random random;

    public SkipList() {
        this.level = 0;
        this.header = new SkipListNode(null, MAX_LEVEL);
        this.random = new Random();
    }

    // 新增：获取当前跳表最大层数（供外部范围查询使用）
    public int getLevel() {
        return this.level;
    }

    // 新增：获取头节点（供外部范围查询使用）
    public SkipListNode getHeader() {
        return this.header;
    }

    private int randomLevel() {
        int level = 0;
        while (random.nextDouble() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    public SkipListNode search(int key) {
        SkipListNode current = this.header;
        //从最高层开始，逐层向下查找
        for (int i = this.level; i >= 0; i--) {
            //在当前层水平移动，知道找到小于或等于目标值的最大节点
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
        }
        //现在在底层，检查下一个节点是否是目标值
        current = current.forward[0];
        //如果下个节点存在并且key相等，则找到目标
        if (current != null && current.key == key) {
            return current;
        }
        return null;//未找到目标
    }

    public boolean insert(int key) {
        // 创建更新数组，用于存储需要更新前向指针的节点
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = this.header;
        // 从最高层开始，查找适合的插入位置
        for (int i = this.level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
            // 记录每一层需要更新的节点
            update[i] = current;
        }
        // 移动到下一个节点
        current = current.forward[0];
        // 检查key是否已经存在
        if (current != null && current.key == key) {
            return false;// key已存在，则插入失败
        }
        // 为新节点生成随机层数
        int randomLevel = randomLevel();
        if (randomLevel > this.level) {
            // 更新跳表当前最大层数
            for (int i = this.level + 1; i <= randomLevel; i++) {
                update[i] = this.header;
            }
            this.level = randomLevel;
        }
        // 创建新的节点
        SkipListNode newNode = new SkipListNode(key, randomLevel);
        // 更新所有受影响的前向指针
        for (int i = 0; i <= randomLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
        return true;
    }

    public boolean delete(int key) {
        // 创建更新数组
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = this.header;
        // 从最高层开始，查找目标节点
        for (int i = this.level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        // 移动到下一节点
        current = current.forward[0];
        // 如果找到目标节点
        if (current == null || current.key != key) {
            return false;
        }
        //从最基层开始，更新所有收到影响层的前向指针
        for (int i = 0; i <= this.level; i++) {
            if (update[i].forward[i] != current) {
                break;
            }
            update[i].forward[i] = current.forward[i];
        }
        // 删除没有元素的层
        while (this.level > 0 && this.header.forward[this.level] == null) {
            this.level--;
        }
        return true;//没有找到目标节点
    }

    public void display() {
        for (int i = this.level; i >= 0; i--) {
            System.out.print("Level " + i + ": ");
            SkipListNode node = this.header.forward[i];
            while (node != null) {
                System.out.print(node.key + " -> ");
                node = node.forward[i];
            }
            System.out.println("null");
        }
    }

    /**
     * 实现Iterable接口的iterator()方法
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            private SkipListNode current = header.forward[0];

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                int key = current.key;
                current = current.forward[0];
                return key;
            }
        };
    }

    public boolean contains(int key) {
        return search(key) != null;
    }

    public int size() {
        int count = 0;
        SkipListNode current = header.forward[0];
        while (current != null) {
            count++;
            current = current.forward[0];
        }
        return count;
    }
}

/**
 * 跳表功能测试类
 */
public class SkipListDemo {
    public static void basicOperationsDemo() {
        System.out.println("=== 基本操作演示 ===");
        SkipList skipList = new SkipList();

        System.out.println("\n插入元素:");
        int[] elements = {3, 6, 7, 9, 12, 19, 17, 26, 21, 25};
        for (int elem : elements) {
            skipList.insert(elem);
            System.out.println("插入 " + elem);
        }

        System.out.println("\n跳表结构:");
        skipList.display();

        System.out.println("\n搜索元素:");
        int[] searchElements = {7, 12, 19, 25, 30};
        for (int elem : searchElements) {
            boolean exists = skipList.contains(elem);
            System.out.println("搜索 " + elem + ": " + (exists ? "存在" : "不存在"));
        }

        System.out.println("\n删除元素:");
        int[] deleteElements = {7, 12, 30};
        for (int elem : deleteElements) {
            boolean success = skipList.delete(elem);
            System.out.println("删除 " + elem + ": " + (success ? "成功" : "失败"));
        }

        System.out.println("\n删除后的跳表结构:");
        skipList.display();

        // 修复2：现在支持for-each遍历（因SkipList实现了Iterable接口）
        System.out.println("\n遍历所有元素:");
        List<Integer> allElements = new ArrayList<>();
        for (int key : skipList) {
            allElements.add(key);
        }
        System.out.println(allElements);
    }

    public static void performanceTest(int n) {
        System.out.println("\n=== 性能测试 ===");
        SkipList skipList = new SkipList();

        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
        Collections.shuffle(data);
        List<Integer> testSample = data.subList(0, 100);

        System.out.println("\n插入 " + n + " 个元素:");
        long startTime = System.nanoTime();
        for (int key : data) {
            skipList.insert(key);
        }
        long endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1e6;
        System.out.printf("耗时: %.6f 秒%n", cost / 1000);

        System.out.println("\n搜索 100 个元素:");
        startTime = System.nanoTime();
        for (int key : testSample) {
            skipList.search(key);
        }
        endTime = System.nanoTime();
        cost = (endTime - startTime) / 1e6;
        System.out.printf("耗时: %.6f 秒%n", cost / 1000);

        System.out.println("\n删除 100 个元素:");
        startTime = System.nanoTime();
        for (int key : testSample) {
            skipList.delete(key);
        }
        endTime = System.nanoTime();
        cost = (endTime - startTime) / 1e6;
        System.out.printf("耗时: %.6f 秒%n", cost / 1000);
    }

    public static void rangeQueryExample() {
        System.out.println("\n=== 范围查询示例 ===");
        SkipList skipList = new SkipList();
        for (int i = 1; i <= 100; i++) {
            skipList.insert(i);
        }

        class RangeQuery {
            List<Integer> query(SkipList skipList, int start, int end) {
                List<Integer> result = new ArrayList<>();
                // 修复3：通过getter获取private成员（header和level）
                SkipListNode header = skipList.getHeader();
                int currentLevel = skipList.getLevel();

                // 从最高层向下查找起始位置
                SkipListNode current = header;
                for (int i = currentLevel; i >= 0; i--) {
                    while (current.forward[i] != null && current.forward[i].key < start) {
                        current = current.forward[i];
                    }
                }

                // 收集范围内的元素
                current = current.forward[0];
                while (current != null && current.key <= end) {
                    result.add(current.key);
                    current = current.forward[0];
                }

                return result;
            }
        }

        RangeQuery rangeQuery = new RangeQuery();
        int[][] ranges = {{10, 20}, {50, 60}, {95, 105}};
        for (int[] range : ranges) {
            int start = range[0];
            int end = range[1];
            List<Integer> result = rangeQuery.query(skipList, start, end);
            System.out.println("范围 [" + start + ", " + end + "] 内的元素: " + result);
        }
    }

    public static void main(String[] args) {
        basicOperationsDemo();
        performanceTest(10000);
        rangeQueryExample();
    }
}